第十三天 Process Synchronization(同步)--下

昨天說完critical section problem的解決方法，今天來說幾個在synchronization常看到的經典問題！

1. Bounded-Buffer Problem：

   假設有n個buffers，每個都有資料，三個semaphore預設值為mutex=1、full=0、empty=n
   Producer要將資料放進去，以下是他的結構圖：
   
   Consumer要將資料取出來，以下是他的結構圖：
   
   經過對比，可以發現他們wait()跟signal()的順序並不同。

2. Readers and Writers Problem：

   有一個data set，有很多process同時共享著。
   Readers：只能讀data set，不能寫，可以同時有多個readers
   Writers：可讀可寫data set，但同時只能有一個writer取得
   Writer和reader考慮的幾種變化，都涉及某種形式的優先事項。
   他們共享的資料有：data set、semaphore rw_mutex預設值為1、semaphore mutex預設值為1、整數read_count預設值為0
   以下是writer process的架構：
   
   以下是reader process的架構：
   
   其中的wait(rw_mutex)，是有人在write;第二個wait(mutex)，是read完後看write有沒有做完。
   Readers and Writers Problem有更進一步的變化，像是：
   First variation：不能讓reader一直等，除非writer可以用shared object
   Second variation：當有一個writer準備好後，立刻write
   上面講的兩種情況，都有可能造成starvation，除非有些系統由kernel提供。

3. Dining-Philosophers Problem：
   
   五個哲學家要吃飯，桌上有五支筷子，而他們只會思考跟吃飯而已，而且不跟隔壁交談。以下有一個架構，這個會造成deadlock，因為大家都拿起右邊的筷子，這樣大家都不能吃飯：
   
   要解決這個deadlock，有幾個解決辦法：

   • 4個人上餐桌
   • 左右筷子都空下來才能吃
   • 非對稱式方法：奇數先取左邊再取右邊，偶數先取右邊再取左邊

   用semaphore解決問題，但他也不保證不會出現deadlock和starvation。

接著我們來說一個厲害的東西，Monitors！

Monitors是高階處理synchronization的方式，但他不是所有作業系統都支援。Monitor由shared data、operations跟initialization code所組成。他本身為Abstract data type，其中有些變數只供自己的procedure使用而已，而同一個時間下，只能以一個process在monitor內活動。雖然他是高階處理synchronization的方式，但還是有一些無法解決的synchronization問題。

在shared data上有condition variable(x,y)，提供programmer設計同步問題時所用。有兩種執行允許在variable上：x.wait()和x.signal()，x.wait()要等到x.signal()才能執行，x.signal()要等恢復x.wait()，如果變數上沒有x.wait()，則變數就沒什麼用。以下是例圖：

如果有兩個process(P和Q)，Ｐ要用x.signal()，Ｑ在x.wait()內，那會出現兩種狀況：

1. Signal and wait -> P要等到Ｑ離開，或是他去等其他的condition
2. Signal and continue -> Q等到Ｐ離開，或是他去等其他的condition
   以上兩種方法各有好壞，由implementer決定用哪種。
   我們來看他如何解決Dining Philosophers的問題：
   
   
   一開始先設定三狀態(思考、餓了、吃飯)
   pickup(int i)拿筷子的方法
   putdown(int i)放下筷子的方法
   test(int i)測試左右有沒有筷子
   雖然這樣可以解決deadlock(一次一個進入)，但是starvation還是有可能會存在。

Process Synchronization我們就講到這啦～～